package arithmetic;


import utils.TreeNode;

/**
 * @author jiangfeng on 2022/3/23
 */
public class BinTree2 {
    /**
     *
     *  二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
     *
     *   注意:
     *
     *   1.同一个节点在一条二叉树路径里中最多出现一次
     *
     *   2.一条路径至少包含一个节点，且不一定经过根节点
     *
     *   给定一个二叉树的根节点root，请你计算它的最大路径和
     *
     *  例如：
     *  给出以下的二叉树，
     *
     *  最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6
     *
     *
     *   数据范围：节点数满足 0 \le n \le 10^50≤n≤10
     *
     *   ，节点上的值满足 |val| \le 1000 ∣val∣≤1000
     *
     *   要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
     */
   
    //    1
    // 2   20
    //    15 10

    public static void main(String[] args) {
        TreeNode TreeNode = new TreeNode(1);
        TreeNode TreeNode2 = new TreeNode(2);
        TreeNode TreeNode20 = new TreeNode(20);
        TreeNode TreeNode15 = new TreeNode(15);
        TreeNode TreeNode10 = new TreeNode(10);
        TreeNode.left = TreeNode2;
        TreeNode.right = TreeNode20;
        TreeNode20.left = TreeNode15;
        TreeNode20.right = TreeNode10;

        System.out.println(getMax(TreeNode));

    }

    static  int  max = 0;
    public static int getMax(TreeNode root){
        maxPathSum(root);
        return max;
    }
    // 思路, 需要一个全局变量记录最大的路径
    public static int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 递归找出左边根节点最大的, 如果路径是负数,则用0代替
        int leftMax = Math.max(0, maxPathSum(root.left));
        int rightMax = Math.max(0, maxPathSum(root.right));
        if (root.left == null && root.right == null) {
            return root.val;
        }
        max = Math.max(max, leftMax + root.val + rightMax);
        return Math.max(leftMax, rightMax) + root.val;
    }
    // //     1
    //  // 1   20
    //   //  15 10
}
